package 广度优先遍历;

import java.util.*;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 课程表.java
 * @Description TODO
 * @createTime 2020年11月09日 15:04:00
 * 现在你总共有 n 门课需要选，记为 0 到 n-1。
 *
 * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
 *
 * 给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
 *
 * 可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
 *
 * 示例 1:
 *
 * 输入: 2, [[1,0]]
 * 输出: [0,1]
 * 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
 *
 *
 * 经典的拓扑排序
 * 具体的知识看广度优先的笔记
 * 思路：queue 队列中始终是【入度为 0 的课】在里面流动
 *       选择一门课，就让它 出列，同时 查看哈希表，看它 对应哪些后续课
 *      将这些后续课的 入度 - 1，如果有 减至 0 的，就将它 推入 queue
 *      不再有新的入度 0 的课入列 时，此时 queue 为空，退出循环
 *
 * 整个流程：1.创建一个数组inDegree用来记录每个课程的入度 只有这个课程的入度为0的时候才可以被学习
 *         2.创建一个哈希表map  key是被依赖元素  value是依赖该元素的数组
 *         3.用一个队列queue维护入度为0的课程 这个课程被学习 就出队 加入结果
 *         4.在哈希表中查找这个元素 把依赖它的所有元素入度减一
 *         5.并且查询当前元素的入度表 如果为0就入队
 *
 *
 *
 */
public class 课程表 {

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //inDegree表示每个课程的入度数量
        int[] inDegree = new int[numCourses];
        //哈希表记录依赖它的课程
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        Queue<Integer> queue = new LinkedList<>();
        //创建入度表和哈希表
        for (int i = 0; i < prerequisites.length; i++) {
            inDegree[prerequisites[i][0]]++;
            if (map.containsKey(prerequisites[i][1])) {
                //如果哈希表包含这个元素 就把第一个元素加到第二个元素的表中
                map.get(prerequisites[i][1]).add(prerequisites[i][0]);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(prerequisites[i][0]);
                map.put(prerequisites[i][1], list);
            }
        }

        /*
         * 到这一步 创建好了入度表和哈希表
         * 入度表是记录当前课程什么时候 可以被学习
         *       也就是说 如果一节课的入度为2则表明 要想学习当前课程 必须学习另外两门之后
         *       只有当它的入度为0的时候才可以被学习
         * 哈希表是记录每个依赖当前课程的其他课程
         *       比如(1,{2,3}) 当1完成的时候 2的入度就可以减一
         * */


        List<Integer> res = new ArrayList<>();

        //用队列来维护入度为0的课程 也就是可以学习的课程
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 出队，查哈希表，将入度为零的入队
        while (!queue.isEmpty()) {
            Integer cur = queue.poll();
            res.add(cur);

            //如果哈希表包含当前元素并且该元素的value不为空
            if (map.containsKey(cur) && map.get(cur).size() != 0) {
                for (Integer num : map.get(cur)) {
                    //依赖当前课程的其他课程的入度减一
                    inDegree[num]--;
                    //当其他课程的入度为0的时候 就放入队列
                    if (inDegree[num] == 0) {
                        queue.offer(num);
                    }
                }
            }
        }
        //使用list的流来转为int[]数组，也可以通过遍历一遍完成转换。
        return res.size() == numCourses ? res.stream().mapToInt(Integer::valueOf).toArray() : new int[0];

    }
    }
}